// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-24 14:48
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.DataStruct.Graph.Dijkstra.DijistraT;

import com.DataStruct.Graph.Dijkstra.DijistraT.Graph.*;

@SuppressWarnings("ALL")
// 一个可更新数据的优先队列，即小顶堆，根据dist构建
public class PriorityQueue {
    // 优先队列中的数组
    private Vertex[] nodes;
    // 队列中的节点个数
    private int count;

    public PriorityQueue(int v) {
        this.nodes = new Vertex[v + 1];
        this.count = 0;
    }

    /**
     * 出队
     *
     * @return
     */
    public Vertex poll() {
        Vertex v = this.nodes[1];
        this.nodes[1] = this.nodes[count--];
        heapify();// 堆化
        return v;
    }

    /**
     * 入队
     *
     * @param vertex
     */
    public void add(Vertex vertex) {
        nodes[++this.count] = vertex;
        int i = this.count;
        /*-----添加元素的同时保持最小堆的结构-----*/
        while (i / 2 > 0 && nodes[i / 2].dist > nodes[i].dist) {
            swap(i / 2, i);
            i = i / 2;
        }
    }

    /**
     * 更新队列中某个节点
     *
     * @param vertex
     */
    public void update(Vertex vertex) {
        for (int i = 1; i < count; i++) {
            if (nodes[i].id == vertex.id) {
                nodes[i] = vertex;
            }
        }
    }

    /**
     * 判空
     *
     * @return
     */
    public boolean isEmpty() {
        if (this.count != 0) {
            return false;
        } else {
            return true;
        }
    }

    // 堆化 -> 只能保证半棵树是最小堆
    private void heapify() {
        int minPos = 1;
        int temp = 1;
        while (true) {
            int left = temp * 2;
            int right = temp * 2 + 1;
            if (left <= count && nodes[left].dist < nodes[temp].dist) {
                minPos = left;
            }
            if (right <= count && nodes[right].dist < nodes[minPos].dist) {
                minPos = right;
            }
            if (minPos == temp) {
                break;
            }
            swap(temp, minPos);
            temp = minPos;
        }
    }

    // 交换两个值
    private void swap(int temp, int minPos) {
        Vertex t = nodes[temp];
        nodes[temp] = nodes[minPos];
        nodes[minPos] = t;
    }
}
